#pragma once
#include <compl/candy.h>


/* 手动实现的fls和ffs, 如果没有__builtin函数则需要自己实现, 通过二分查找法可以取得log(n)的复杂度 */
CSAI int __fls(unsigned int v)
{
	int n = 32;

	if (!v) return -1;
	if (!(v & 0xFFFF0000)) { v <<= 16; n -= 16; }
	if (!(v & 0xFF000000)) { v <<=  8; n -= 8;  }
	if (!(v & 0xF0000000)) { v <<=  4; n -= 4;  }
	if (!(v & 0xC0000000)) { v <<=  2; n -= 2;  }
	if (!(v & 0x80000000)) { v <<=  1; n -= 1;  }

	return n - 1;
}

CSAI int __fls64(unsigned long v)
{
	int n = 64;

	if (!v) return -1;
	if (!(v & 0xFFFFFFFF00000000)) { v <<= 32; n -= 32; }
	if (!(v & 0xFFFF000000000000)) { v <<= 16; n -= 16; }
	if (!(v & 0xFF00000000000000)) { v <<=  8; n -= 8;  }
	if (!(v & 0xF000000000000000)) { v <<=  4; n -= 4;  }
	if (!(v & 0xC000000000000000)) { v <<=  2; n -= 2;  }
	if (!(v & 0x8000000000000000)) { v <<=  1; n -= 1;  }

	return n - 1;
}

CSAI int __ffs(unsigned int v)
{
	int n = 1;

	if (!v) return -1;
	if (!(v & 0x0000FFFF)) { v >>= 16; n += 16; }
	if (!(v & 0x000000FF)) { v >>=  8; n += 8;  }
	if (!(v & 0x0000000F)) { v >>=  4; n += 4;  }
	if (!(v & 0x00000003)) { v >>=  2; n += 2;  }
	if (!(v & 0x00000001)) { v >>=  1; n += 1;  }

	return n - 1;
}

CSAI int __ffs64(unsigned long v)
{
	int n = 1;

	if (!v) return -1;
	if (!(v & 0x00000000FFFFFFFF)) { v >>= 32; n += 32; }
	if (!(v & 0x000000000000FFFF)) { v >>= 16; n += 16; }
	if (!(v & 0x00000000000000FF)) { v >>=  8; n += 8;  }
	if (!(v & 0x000000000000000F)) { v >>=  4; n += 4;  }
	if (!(v & 0x0000000000000003)) { v >>=  2; n += 2;  }
	if (!(v & 0x0000000000000001)) { v >>=  1; n += 1;  }

	return n - 1;
}
